package InterviewTest.q1719_missingTwo;

public class Solution_2 {
    /*
    我们以 1 2 3 4 5 6 7 8 9 10 为例
    假设缺失了 7 8
    我们用异或找出来的temp是7 ^ 8 那么用j找其中一个值为1的位 由于7 ^ 8为 1111
    所以我们找出来第一位就是1 也就是7 和 8首位就存在不同
    根据首位不同 我们分开异或两组数
    也就是1 2 3 4 5 6 7 8 9 10 和 1 2 3 4 5 6 9 10
    首位为1的数有1 3 5 7 9 那么除了7之外 其他的1 3 5 9都异或了两次消除掉了 剩下7
    首位为0的数则为剩下的 异或两次消除后剩下8
    就能够找出两个数字
     */
    public int[] missingTwo(int[] nums) {
        int N = nums.length + 2;

        // 1.用temp记录所缺两个数字的异或
        int temp = 0;
        for (int num : nums) temp ^= num;
        for (int i = 1; i <= N; i++) temp ^= i;

        // 2.用j记录temp的32个位中其中一个值为1的位（两个数字的异或中某位为1，说明这两个数字的这个位的值不同）
        int j;
        for (j = 0; j < 32; j++) {
            if (((temp >> j) & 1) == 1) break;
        }

        // 3.用num1，num2记录两个缺失的数，依据记录的j位进行分组异或，j位为1的数跟num1异或，j位为2的数跟num2异或
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if ((num >> j & 1) == 1) num1 ^= num;
            else num2 ^= num;
        }
        for (int i = 1; i <= N; i++) {
            if ((i >> j & 1) == 1) num1 ^= i;
            else num2 ^= i;
        }

        // 4.返回结果
        return new int[]{num1, num2};



    }
}
